#ifndef DLIST_H
#define DLIST_H
#ifndef CONTAINER_H
#include "Container.h"
#define CONTAINER_H
#endif

using namespace std;
#include <string>


template <class T>

class Node_t{

public:

	Node_t(T* v = 0,Node_t<T>* nex = 0,Node_t<T>* pre = 0) :
	  val(v),next(nex),prev(pre){}

	T* val;

	Node_t<T>* next;

	Node_t<T>* prev;

	
};


template <class T>

class Dlist_t : public Container_t<T>{

public:

	Dlist_t() : Container_t<T>(), head (new Node_t<T>()), tail (new Node_t<T>())
	{
		init();
	}

	Dlist_t(const Dlist_t<T>& other) : Container_t<T>(), head (new Node_t<T>()), tail (new Node_t<T>())
	{
		init();	
		Node_t<T> *pnode = other.head; 
		while ((pnode = pnode->next) != other.tail){
			insert(pnode->val);
		}
	}

	void insert(T* const val)
	{
		insertAt(val,tail);
	}

	T* find(const T& element) const{
		return (locate(element))->val;
	}

	void append(T* const element, int index)
	{
		if (index > size-1) {
			throw std::string("Array: Illegal index");
			return;
		}
		Node_t<T> *pnode =locateIndex(index);
		insertAt(element,pnode->next);
	}

	void prepend(T* const element, int index)
	{
		if (index < 0) {
			throw std::string("Array: Illegal index");
			return;
		}
		Node_t<T> *pnode =locateIndex(index);
		insertAt(element,pnode);
	}

	T* remove(const T& element) {
		Node_t<T> *pnode =locate(element);
		T* val = pnode->val;
		removeNode(pnode);
		return val;
	}

	void removeAll()
	{
		Node_t<T>* cursor = head->next;
		while (cursor != tail){
			cursor = cursor->next;
			delete cursor->prev;
			size--;
		}
		init();
	}

	void removeAndDeleteAll()
	{
		Node_t<T>* cursor = head->next;
		while (cursor != tail){
			cursor = cursor->next;
			delete cursor->prev->val;
			delete cursor->prev;
			size--;
		}
		init();
	}

	Node_t<T>* reset()
	{
		return current = head;
	}

	Node_t<T>* next()
	{
		Node_t<T>* next = current->next;
		if (next != 0) current=next;
		return next;
	}
	
	Node_t<T>* prev()
	{
		Node_t<T>* prev = current->prev;
		if (prev != 0) current=prev;
		return prev;
	}

	~Dlist_t()
	{
		removeAll();
		delete head;
		delete tail;
	}
	

protected:

	Node_t<T>* current;

	Node_t<T>* head;

	Node_t<T>* tail;

	void init()
	{
		head->next = tail;

		tail->prev = head;

		current = head;
	}

	Node_t<T>* locate(const T& element) const
	{
		Node_t<T> *pnode = head;
		while ((pnode = pnode->next) != tail){
			if (*(pnode->val) == element) break;
		}
		return pnode;
	}

	Node_t<T>* locateIndex(int index) const
	{
		if (index < 0) return head;
		int i = 0;
		Node_t<T> *pnode = head;
		while ((pnode = pnode->next) != tail){
			if (i++ == index) break;
		}
		return pnode;
	}

	void insertAt(T* val,Node_t<T> *cursor)
	{
		Node_t<T> *pnode = new Node_t<T>(val,cursor,cursor->prev);
		cursor->prev->next = pnode;
		cursor->prev = pnode;
		size++;
	}

	void removeNode(Node_t<T> *pnode)
	{
	if (pnode != tail && pnode != head){
		Node_t<T> *prev= pnode->prev;
		Node_t<T> *next= pnode->next;
		prev->next = next;
		next->prev = prev;
		delete pnode;
		size--;
		}
	}
	//implementing this method will be used for the assign constructor
	void copyToContainer(Container_t<T>* other) const
	{
		other->removeAll();
		Node_t<T> *pnode = head; 
		while ((pnode = pnode->next) != tail){
			other->insert(pnode->val);
		}
	}

};

#endif //DLIST_H